挑战赛#26题解 | 非官方
本次题目猜测的总体难度如下,仅供参考:
题目编号 题目标题 难度 T1 小午的四舍五入 入门\color{red}{入门}入门 T2 小午的排名预期 入门\color{red}{入门}入门 T3 午枫的玩具火车 普及−\color{orange}{普及-}普及− T4 午枫的身高统计 普及−\color{orange}{普及-}普及− T5 小午的学习技能 普及−\color{orange}{普及-}普及− T6 小午的迷宫 普及−\color{orange}{普及-}普及−
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1. 小午的四舍五入
题目大意
给你一个实数 nnn,要你将 nnn 四舍五入至整数最低位。
解题思路
可以使用 round() 函数,将 double 类型的数四舍五入。
参考代码
时间复杂度:O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2. 小午的排名预期
题目大意
每天考试的分数为 300300300 分,现在有 nnn 名考生,第 iii 名考生第一,二,三天的分数分别为ai,1,ai,2,ai,3a_{i,1}, a_{i, 2}, a_{i, 3}ai,1 ,ai,2 ,ai,3 。想请问,第 iii 名学生在考完第四天试后,能达到前 kkk 名吗?
解题思路
可以使用结构体,把前三天的总分加起来,再用 idxidxidx 记下编号。使用结构体排序,然后找出第 kkk 名,其次,遍历每位考生。假设第 iii 为考生那天获得了 300300300 分,其他都拿 000 分,那么这位考生能获得前 kkk 名的判断为 ai.sum+300≥ak.suma_i.sum + 300 \geq a_k.sumai .sum+300≥ak .sum,再用 visvisvis 数组记录下来输出即可。
参考代码
时间复杂度:O(nlogn)O(n log n)O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3. 午枫的玩具火车
题目大意
有一个 nnn 节车厢的火车,编号为 1∼n1 \sim n1∼n,一开始每一节车厢之间都是断开的。现在有三种操作:
* 1 x y 是把车厢 xxx 的尾部和车厢 yyy 的尾部链接。
* 2 x y 是把车厢 xxx 的尾部和车厢 yyy 的尾部断开。
* 3 x 是输出包含车厢 xxx 的火车中所有车厢的编号,从头到尾输出。输出时第一个数字为列车的长度。
总共执行 qqq 次操作。
解题思路
我们可以使用数组来模仿双向链表,实现连接和断开的操作。其中,没有连接(断开)在数组中表示为 −1-1−1,其他则表示为连接了的车厢编号。
参考代码
时间复杂度:O(q×L)O(q \times L)O(q×L),其中 LLL 表示链表的最大长度。最坏情况为 O(q×n)O(q \times n)O(q×n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4. 午枫的身高统计
题目大意
给你 nnn 个人的身高,第 iii 个人的身高为 aia_iai 。接下来,进行 qqq 次询问,判断身高大于等于 xxx 的人有多少个。
解题思路
可以使用 lower_bound() 函数,找出第一个不小于 xxx 的值的下标,再拿总人数减去结果即可。
参考代码
时间复杂度:O((n+q)logn)O((n + q) log n)O((n+q)logn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5. 小午的学习技能
题目大意
总共有 nnn 个技能,每个技能都有一个学习时间,第 iii 个技能需要花费 tit_iti 的时间,而第 iii 个技能有 mim_imi 个前置技能,ai,ja_{i,j}ai,j 表示第 iii 个技能的第 jjj 个前置技能。现在,请你求出完成第 nnn 个技能需要花费的最少时间。
解题思路
我们可以使用递归的思路,创建一个 visvisvis 数组,visivis_ivisi 表示第 iii 个技能是否学习过。然后使用逆向思维,从第 nnn 个技能开始,然后遍历所有的前置技能,然后重复这个步骤即可。
参考代码
时间复杂度:O(n+E)O(n + E)O(n+E),其中 EEE 表示 ∑mi\sum m_i∑mi 。O(n+E)O(n + E)O(n+E) 最大 ≈O(4×105)\approx O(4 \times 10 ^ 5)≈O(4×105)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6. 小午的迷宫
题目大意
有一个 n×mn \times mn×m 的迷宫,迷宫里分别有障碍物 # 和无障碍路径 . 。小午从迷宫的 (1,1)(1, 1)(1,1) 作为起点,每次只能向下或者向右走一格。问,他能经过的格子数量最多是多少呢?
解题思路
可以用一个二维 dpdpdp 数组,遍历所有点,而 dpdpdp 的转移方程就是 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1,这样可以在这格的基础上,找上和左的点,从到达的点数更多的点走到当前个,最后取 maxmaxmax 即可。
参考代码
时间复杂度:O(n×m)O(n \times m)O(n×m)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------